Người tiền sử đã xuất hiện trên Vịnh Hạ Long từ rất lâu. Qua nhiều năm khảo cổ, các nhà nghiên cứu kết luận rằng trong suốt tiến trình sơ sử, ba nền văn hóa mang tên Soi Nhụ-Cái Bèo-Hạ Long trên khu vực vịnh cho thấy vịnh Hạ Long và khu vực lân cận một thời từng là cái nôi văn hóa của nhân loại.

Vùng đất trung tâm của thành phố Hạ Long ngày nay, xưa kia chỉ là một làng chài ven biển, có tên là Bãi Hàu.

Đến đầu thời Nguyễn được đổi tên thành xã Mẫu Lệ. Về sau, hình thành thêm các xã Hà Lầm, Lũng Phong, Giang Võng và Trúc Võng. Các xã phường phía Đông và phía Tây của thành phố hiện nay, trước đó đều thuộc huyện Hoành Bồ.

Năm 1883, Pháp chiếm vùng vịnh Hạ Long, họ tiến hành khai thác than ở các mỏ trên bờ vịnh. Có ý kiến cho rằng do trên các đảo ở đây có nhiều cây gai nên người Pháp gọi là lle des brouilles, phiên âm là Hon Gai hay Hon Gay, sau đổi thành Hòn Gai. Còn theo các nhà nghiên cứu thì Hòn Gai là cách gọi lệch của người Pháp từ địa danh Hồng Hải lúc bấy giờ. Do tiếng Pháp âm H là âm câm. Nên đọc là Hongay hay Hòn Gai sau này. Lúc bấy giờ, Hòn Gai là một đơn vị hành chính trực thuộc tỉnh Quảng Yên.

Sau Cách mạng tháng 8 năm 1945, thị xã Hồng Gai trở thành thủ phủ của vùng mỏ. Cuối năm 1946, người Pháp tái chiếm Hòn Gai.

Sau hiệp định Genève 1954, thị xã Hồng Gai lại là thủ phủ của khu Hồng Quảng.

Ngày 17 tháng 6 năm 1958, xã Thành Công thuộc huyện Hoành Bồ được sáp nhập vào thị xã Hòn Gai.[7]

Ngày 30 tháng 10 năm 1963, tỉnh Hải Ninh và khu Hồng Quảng hợp nhất thành tỉnh Quảng Ninh, từ đó Hồng Gai trở thành thủ phủ của Quảng Ninh[8].

Ngày 26 tháng 9 năm 1966, chuyển xã Tân Hải về huyện Cẩm Phả quản lý.[9]

Thị xã Hồng Gai là trung tâm cung cấp than cho toàn bộ ngành công nghiệp của Miền Bắc xã hội chủ nghĩa, là cửa ngõ nối với Trung Quốc nên trở thành trọng điểm đánh phá ác liệt của Mỹ trong chiến tranh. Bến phà Bãi Cháy (ngừng hoạt động năm 2007, nay được thay thế bằng cầu Bãi Cháy) đã từng là đầu mối giao thông quan trọng, bị bom Mỹ hủy diệt nhiều lần, 3 lần danh hiệu Anh hùng lực lượng vũ trang nhân dân.

Sau năm 1975, thị xã Hồng Gai có 4 phường: Bạch Đằng, Hạ Long, Trần Hưng Đạo, Yết Kiêu; 5 thị trấn: Bãi Cháy, Cao Thắng, Cọc 5, Hà Lầm, Hà Tu và 3 xã: Hùng Thắng, Thành Công, Tuần Châu.

Ngày 16 tháng 1 năm 1979, chia thị trấn Bãi Cháy thành 2 thị trấn: Bãi Cháy và Giếng Đáy.[10]

Ngày 11 tháng 8 năm 1981, chia thị trấn Hà Tu thành 2 phường: Hà Tu và Hà Phong; chia thị trấn Hà Lầm thành 3 phường: Hà Lầm, Hà Trung, Hà Khánh; chia thị trấn Cọc 5 thành 2 phường: Hồng Hà và Hồng Hải; chia thị trấn Cao Thắng thành 2 phường: Cao Thắng và Cao Xanh; chia thị trấn Giếng Đáy thành 2 phường: Giếng Đáy và Hà Khẩu; chuyển thị trấn Bãi Cháy thành phường Bãi Cháy.[11]

Ngày 28 tháng 5 năm 1991, sáp nhập xã Thành Công vào phường Hà Khẩu.

Ngày 27 tháng 12 năm 1993, Chính phủ bàn hành Nghị định số 102-CP, thành lập thành phố Hạ Long trên cơ sở toàn bộ diện tích và dân số của thị xã Hồng Gai.[1]

Ngày 28 tháng 10 năm 1996, phường Hạ Long được đổi tên thành phường Hồng Gai.[12]

Ngày 16 tháng 8 năm 2001, các xã Việt Hưng và Đại Yên thuộc huyện Hoành Bồ được sáp nhập vào thành phố Hạ Long.[13]

Ngày 26 tháng 9 năm 2003, thành phố Hạ Long được công nhận là đô thị loại II.[14]

Ngày 1 tháng 10 năm 2003, chuyển 2 xã Hùng Thắng và Tuần Châu thành 2 phường có tên tương ứng.[15]

Ngày 5 tháng 2 năm 2010, chuyển 2 xã Đại Yên và Việt Hưng thành 2 phường có tên tương ứng.[16]

Ngày 10 tháng 10 năm 2013, Chính phủ ban hành Quyết định số 1838/QĐ-TTg công nhận thành phố Hạ Long là đô thị loại I trực thuộc tỉnh Quảng Ninh.[2]

Đến cuối năm 2018, thành phố Hạ Long có 20 đơn vị hành chính trực thuộc, gồm 20 phường: Bạch Đằng, Bãi Cháy, Cao Xanh, Cao Thắng, Đại Yên, Giếng Đáy, Hà Khánh, Hà Khẩu, Hà Lầm, Hà Phong, Hà Trung, Hà Tu, Hồng Gai, Hồng Hà, Hồng Hải, Hùng Thắng, Trần Hưng Đạo, Tuần Châu, Việt Hưng, Yết Kiêu.

Ngày 17 tháng 12 năm 2019, Ủy ban thường vụ Quốc hội thông qua Nghị quyết số 837/NQ-UBTVQH14 về việc sắp xếp các đơn vị hành chính cấp huyện, cấp xã thuộc tỉnh Quảng Ninh[17]. Theo đó:

• Sáp nhập toàn bộ 843,54 km² diện tích tự nhiên và 51.003 người của huyện Hoành Bồ (gồm thị trấn Trới và 12 xã: Bằng Cả, Dân Chủ, Đồng Lâm, Đồng Sơn, Hòa Bình, Kỳ Thượng, Lê Lợi, Quảng La, Sơn Dương, Tân Dân, Thống Nhất, Vũ Oai) vào thành phố Hạ Long.
• Thành lập phường Hoành Bồ thuộc thành phố Hạ Long trên cơ sở toàn bộ diện tích và dân số của thị trấn Trới.

Thành phố Hạ Long có 21 phường và 12 xã như hiện nay.